package com.wu.leetcode.sort.radixsort;

import java.util.Arrays;

/**
 * @author lynn
 * @date 2020/7/12 - 10:40
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void radixSort(int[] arr) {
        //基数排序
        //创建一个二维数组 共十个， 代表桶的位置
        //思想：先将每个数按个位数排序 依次放入桶中

        //创建二维数组，为了防止数据溢出 每个桶的初始大小设为数组的长度
        //有十个桶 每个桶最多放置arr数组长度的数据
        int[][] bucket = new int[10][arr.length];

        //为了方便记录每个桶中数据的个数，创建一个一维数组
        //例如 bucketElementCount[0]就代表0号桶中数据的个数
        int[] bucketElementCount = new int[10];

        //使用for循环来简化代码
        //获取数组最大元素的长度
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //获取长度
        int maxLength = (max + "").length();
        //根据数的位数
        for (int k = 0; k < maxLength; k++) {
            for (int i = 0; i < arr.length; i++) {
                //获取每个元素对应的位数,digit就代表几号桶
                int digit = arr[i] / (int) (Math.pow(10, k)) % 10;
                //此处bucketElementCount[digit] 为0 因为未初始化 默认为0 刚好代表下标
                bucket[digit][bucketElementCount[digit]] = arr[i];
                //代表digit号桶中的数据加1，且后移 方便存储下一个位置
                bucketElementCount[digit]++;
            }

            //按照桶的顺序 依次取出放入arr数组中
            int index = 0;
            //遍历每个桶
            //先判断桶中是否有数据
            for (int i = 0; i < bucketElementCount.length; i++) {
                if (bucketElementCount[i] != 0) {
                    for (int j = 0; j < bucketElementCount[i]; j++) {
                        arr[index++] = bucket[i][j];
                    }
                }
                //注意 每次循环完毕 将桶内的数据清零 方便下次存放
                bucketElementCount[i] = 0;
            }
        }
    }
}
